Batch 2 - Class 55 - Logic - Induction II

• Answer: A,B,C,D,E,F have 15,14,13,10,11,12 respectively
• Solution 1: Smiti had a great solution. Once it is clear that D must have 5 in the second round, she just flipped the scores for 3rd and 4th rounds relative to 1st and 2nd round. This brought everyone to a score of 10. Then simply get A a 5 in the last round
• Solution 2: Someone I was interviewing last week gave this solution. The second round is obvious. After that, focus on giving a zero to the person with highest score at end of each round to make him lose (and not on making A win). And last round, give A a 5
• Solution 3: Opposite sitting players total at end of 5 games must be 25 for each pair. So A must have at least 14 (because someone in other pairs must have at least 13). This means D can have at most 11, and he already has 9 in first two rounds. So D must have a zero in some round. Since order of rounds is not important, lets say D has a zero in 3rd round. On last two rounds, D's possibilities (given he can only score 2 more points) are 00, 01, 11, or 02. We can test each of these in turn.

• Difference relative to deduction? From specific to general.
• Steps in Induction proofs
• The Hypothesis

  Trick to forming a hypothesis - solve for smallest 4-5 cases - try to spot the pattern
• Basis Step
• Induction Step - Note that Induction step only assumes that the hypothesis holds upto "n", and not in general - that is what we are trying to prove.
• Prove that the sum of first n natural numbers is n(n+1)/2
• Note that some problems, like this one, can be proved in multiple ways, including induction
• Alternate proof?
• (MC - 9 - 4) Tower of Hanoi - explain the problem to students. Is it always possible to move all the rings to one of the free spindles? How?
• Introduce "recursion" - Note that it is more than a proof of a mathematical formula. Recursion is a procedure of solving the problem - the "how" and not just the "what"
• Can you figure out the number of moves to make the transfer? Apply induction to prove (2^n -1)

• (Cornell) Two people have two consecutive natural numbers pasted on their heads, which they can't see but the other person can see. First person starts by asking the other if she knows what her number is. If she says yes, game ends. If she says no, she asks the first person if he knows his number. And so on. Does the game ever end? Sometimes? Never? Always?
• Let kids think -intuitively, the answer is that the game doesn't end

  Ask someone what is your name repeatedly to reinforce this false intuition - it seems that asking the same question again and again doesn't help
• What if the second person sees a number 1 on first person's forehead? Oh, so it does finish in some cases? Which ones?
• What if first person sees a number "2" on second person's forehead? What can he reason by hearing a "no" from the second person? What if there is a "4" on one person's head?
• Can we form an induction hypothesis?

  The game ends in at most 2n steps, if n is the lower of the two numbers

  Note that in some cases, forming the hypothesis can be challengingBase case is already provenProve the induction step
• Caution - Wrong Proofs using Induction - let the kids spot the errors
• (Decade - 6 - Section 6 - 1) All natural numbers are even - Assume that any natural number up to n is even. We want to prove that n+1 is also even. Since n+1=n-1+2. What's wrong?
• We have not proven our base hypothesis. 1 is odd
• (Decade - 6 - Section 6 - 2) All dogs are the same color - Basis step: 1 dog is obviously of the same color. Take n+1 dogs. If all sets of n dogs are the same color, then take a dog A out and rest must be of same color. Now take a dog B out and rest must be of same color. In the dogs left in both cases, there is a dog C, which is common. And hence the two sets need to be of same color. Hence proved.
• We have assumed at least three dogs, so we must prove for 2 dogs, not just for one. Our induction step doesn't hold for 2 dogs.

• (Cornell) Natives Puzzle - Natives in a certain colony have a myth that there is a certain disease signaled by a blue mark on their forehead. If they find out that they have the disease, they must declare it the very next day in the townhall meeting, and leave the colony. However, no one else tells others if they have a blue mark out of courtesy. One day, a foreigner comes in, and tells the whole society that he has seen at least one blue mark in the colony. What will happen?

  We have done this problem before - now we can solve it using induction
• What happens if all the natives have a blue mark on their forehead? And why does a foreigner telling them help, since they already know the fact being stated?
• (Cornell) Pirates Puzzle - There are 13 pirates, who find a pot of cold coins. Pirates are ranked by hierarchy. The leader must propose a distribution, and others must vote. A tie results in the proposal being passed. Otherwise, the leader/proposer is killed, and the next leader proposes a distribution. Pirates are greedy, but given all equal, they don't want to kill their fellow pirates because it makes the gang weaker. What is the final distribution?
• Solve for small number of pirates - see the pattern
• Form a hypothesis
• Base case is already proven by now
• Prove the induction step